// https://leetcode.cn/problems/coin-lcci/
// Created by ade on 2022/9/16.
// 硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int M = 1000000007;
    vector<int> coins = {1, 5, 10, 25};
    int sum = 0;

    int waysToChange(int n) {
        dfs(n);
        return sum;
    }

    void dfs(int n) {
        if (n == 0) {
            sum++;
            sum = sum >= M ? sum - M : sum;
            return;
        }
        for (auto &coin : coins) {
            if (n < coin) return;
            n -= coin;
            dfs(n);
            n += coin;
        }
    }

};

int main() {
    Solution so;
    int n = 10;
    cout << so.waysToChange(n);
    return 0;
}